package Graph.Medium;

import java.util.List;

public class LC0841 {
    /**
     * 本质上是有向无权图的深度优先遍历；rooms是图的邻接表
     */
    public boolean canVisitAllRooms(List<List<Integer>> rooms) {
        int n = rooms.size();
        boolean[] visited = new boolean[n];
        dfs(rooms, 0, visited);

        for (boolean canVisit : visited) {
            if (!canVisit) return false;
        }

        return true;
    }

    private void dfs(List<List<Integer>> adjLists, int startFrom, boolean[] visited) {
        visited[startFrom] = true;
        List<Integer> adjList = adjLists.get(startFrom);
        for (int j = 0; j < adjList.size(); j++) {
            int v = adjList.get(j); // 邻接顶点
            if (!visited[v]) dfs(adjLists, v, visited);
        }
    }
}
